Traffic management is important in digital networks. Traffic management involves the controlling and scheduling of traffic through paths established through the network. One design consideration faced by traffic management systems is the concept of head-of-line blocking, in which two or more streams of traffic are competing for the same resources. In head-of-line blocking schemes, it is a goal to protect the stream(s) of traffic that is/are in profile, and to push back on the offending stream(s). FIG. 1 illustrates a common description of this scheme. Traffic streams from Source A (reference numeral 2) and Source B (reference numeral 3) are delivered via common pipes 4 and 5 to Destination C (reference numeral 6) and Destination D (reference numeral 7). As shown, Destination C can no longer take traffic from Stream Y, and pushes the traffic back on common pipe 4 sourcing the Stream Y traffic to stop Stream Y. However, Stream X and Stream Y use the same common pipe 4 which raises a question as to how to keep from blocking Stream X when Stream Y can no longer be sent. This problem becomes even more difficult if the common pipe 4 is already full of Stream Y traffic. Hence, a solution is needed to bypass the Stream Y traffic in common pipe 4 without hindering the overall performance of common pipe 4.
FIG. 2 illustrates another important and related concept to digital networks, traffic shaping. Traffic shaping involves buffering traffic and sending traffic based upon a desired profile. A traffic profile can include, but is not limited to the following properties: a level of priority relative to other traffic, buffer depth, latency through the buffer, jitter in sending the traffic contained in the buffer, and a rate at which the traffic should be sent. One common approach to traffic shaping involves the use of a queuing system to manage the profile. As traffic arrives, it is placed on the queue. The traffic is de-queued based upon its assigned drain rate. This is illustrated in FIG. 2. A single stream of traffic arrives at the input such that the output approaches the desired output rate 10. The desired output rate is depicted by the dotted line 12. It is highly desirable to smooth the input such that the output approaches the desired output rate 12.
To perform cost effective shaping of traffic, a traffic shaping device should be able to shape a large number of traffic profiles, as shown in FIG. 3. More particularly, FIG. 3 shows several input streams 10, 14, and 16 and desired outputs 12, 18 and 20 for those input streams. Supporting (and uniquely shaping) large numbers of traffic streams means supporting a large number of queues. However, traditional queuing structures do not scale well due to the exponential growth of instancing each queuing engine, and arbitration mechanisms that are needed to aggregate the resulting dequeued traffic to be sent. This implies that supporting a large number of queues using traditional queuing structure is inherently not cost effective.
Accordingly, a system and method are needed to avoid head-of-line blocking at line rate in order to allow for better profiling, shaping and servicing of traffic. Furthermore, improvements are needed that enable a higher utilization of ports served by a queuing structure.